package com.skh.string;

/**
 * @Author skh
 * @Date 2020/3/28 11:40
 * @Desc 制造字母异位词的最小步骤数
 */
public class MinSteps {
    /**
     * 给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的 任一字符 替换为 另一个字符。
     *
     * 返回使 t 成为 s 的字母异位词的最小步骤数。
     *
     * 字母异位词 指字母相同，但排列不同的字符串。
     *
     *  
     *
     * 示例 1：
     *
     * 输出：s = "bab", t = "aba"
     * 输出：1
     * 提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。
     * 示例 2：
     *
     * 输出：s = "leetcode", t = "practice"
     * 输出：5
     * 提示：用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 变成 s 的字母异位词。
     * 示例 3：
     *
     * 输出：s = "anagram", t = "mangaar"
     * 输出：0
     * 提示："anagram" 和 "mangaar" 本身就是一组字母异位词。
     * 示例 4：
     *
     * 输出：s = "xxyyzz", t = "xxyyzz"
     * 输出：0
     * 示例 5：
     *
     * 输出：s = "friend", t = "family"
     * 输出：4
     *
     */

    /**
     * 常规 hash
     * 既然 t 与 s 长度相同，那么我们只需要知道 t 中的每一种字母的出现频次和 s 中每一种字母的出现频次。然后将 t 中的字母替换即可
     */
    public int minSteps(String s, String t) {
        int step = 0;

        int[] countS = new int[26];
        int[] countT = new int[26];

        for (int i = 0; i < s.length(); i++) {
            countS[s.charAt(i)-'a']++;
            countT[t.charAt(i)-'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (countS[i] == 0) {
                //s没有,t有
                step += countT[i];
            } else if (countS[i] < countT[i]) { //替换多余的部分
                step += countT[i] - countS[i];
            }
        }

        return step;
    }

    /**
     * 空间压缩
     * 我们可以只用一个计数器计算 s 中字母的频率，用 t 减少计数器中的每个字母的频次，最后，字母频次大于 0 列入步骤数 step 中
     */
    public int minSteps1(String s, String t) {
        int step = 0;

        int[] counter = new int[26];

        for (int i = 0; i < s.length(); i++) {
            counter[s.charAt(i)-'a']++;
            counter[t.charAt(i)-'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (counter[i] > 0) {
                step += counter[i];
            }
        }

        return step;
    }
}
